AUTHORS: Songsong Dai, Sizhao Li, Yangbing Wu, Donghui Guo

Download as PDF

ABSTRACT: A conference key distribution is a scheme that allows the designated subset of users to compute a shared key for secure communication. In this paper we analyze secure instances of conference key distribution based on the ideas of Kolmogorov complexity. First, Kolmogorov complexity is used as a measure of the individual security in conference key distribution, we present a model for conference key distribution in terms of Kolmogorov complexity. Then, Kolmogorov complexity is used as a measure of the amount of randomness needed by secure instances of conference key distribution. Thus we give the lower bounds holding in the model for each user needed to store. Moreover, we give lower bounds on the amount of information in conference key distribution for various types of combinatorial structures

KEYWORDS: Cryptography, Conference key distribution, Combinatorial design, Cryptographic security, Kolmogorov complexity

REFERENCES:

[1] Alimomeni, M., Safavi-Naini, R.: Guessing secrecy. In: Proc. of the 6th International Conference on Information Theoretic Security (ICITS 2012), LNCS7412, Springer-Verlag, pp.1–13 (2012).

[2] Allender, E.: Some consequences of the existence of pseudorandom generators. J. Comput. System Sci.,Vol. 39, pp.101-124 (1989).

[3] Antunes, L., Laplante, S., Pinto, A., et al.,: Cryptographic security of individual instances. In Proc. 3th Int. Conf. on Information Theoretical Security (ICITS 2007), Madrid, Spain, May 25-29, LNCS 4883, Springer, Berlin Heidelberg, pp. 195-210 (2009).

[4] Antunes, L., Matos, A., Pinto, A., Souto, A., Teixeira, A.: One-Way Functions Using Algorithmic and Classical Information Theories. Theory Comput Syst. 52(1), 162–178 (2013).

[5] Blom R.: An optimal class of symmetric key generation systems. In: EUROCRYPT, 1984. Lecture Notes in Computer Science, vol. 209, pp. 335–338 (1985).

[6] Blundo C., D’Arco P.: An Information Theoretic Model for Distributed Key Distribution, In: Proceedings of the 2000 IEEE International Symposium on Information Theory, p. 270, (2000).

[7] Blundo C., D’Arco P.: Analysis and Design of Distributed Key Distribution Centers, J. Cryptology 18 391414 (2005).

[8] Blundo C., De Santis A., Herzberg A., Kutten S., Vaccaro U., Yung M.: Perfectly Secure Key Distribution for Dynamic Conferences, Inf. Comput. 146(1) : 1–23(1998).

[9] Blundo C., De Santis A., Vaccaro, U.: Randomness in Distribution Protocols, Inf. Comput. 131: 111–139(1996).

[10] Bose M., Dey A., Mukerjee R.: Key predistribution schemes for distributed sensor networks via block designs. Des. Codes Cryptogr. 67, 111- 136.(2013)

[11] C¸ amtepe S., Yener B .: Combinatorial design of key distribution mechanisms for wireless sensor networks. IEEE/ACM Trans. Netw. 15, 346-358 (2007).

[12] Dai, S., Guo, D.: Comparing security notions of secret sharing schemes. Entropy, 17, 1135-1145 (2015).

[13] Dodis, Y.: Shannon Impossibility, Revisited, In: Proc. 6th Int.Conf. on Information Theoretical Security (ICITS 12), Montreal, QC, August 15- 17, Springer, Berlin. 2012, pp.100–110.

[14] Dong J., Pei D., Wang X.: A key predistribution scheme based on 3-designs. In: INSCRYPT 2007. Lecture Notes in Computer Science, vol. 4990, pp. 81-92, Springer, Berlin (2008).

[15] Fiat A., Naor M.: broad cast encryption , Advances in Cryptology-CRYPTO 1993, D. Stinson(Ed.), LNCS 773, Springer-Verlag, pp. 480- 491, 1994.

[16] Fuller, B., O’Neill, A., Reyzin, L.: A unified approach to deterministic encryption: New constructions and a connection to computational entropy. J. Cryptol. 2013, DOI: 10.1007/s00145- 013-9174-5.

[17] Iwamoto, M., Shikata, J.: Information theoretic security for encryption based on conditional Renyi entropies, Information Theoretic Se- ´ curity. Springer International Publishing, 2014, pp.103–121

[18] Kaced, T.: Almost-perfect secret sharing, Information Theory Proceedings (ISIT), 2011, IEEE International Symposium on. IEEE, pp. 1603- 1607 (2011).

[19] Lee J., Stinson D.R.: A combinatorial approach to key predistribution for distributed sensor networks. In: IEEE Wireless Communications and Networking Conference (WCNC 2005), vol. 2 , pp. 1200-1205.

[20] Lee J., Stinson D.R.: Common intersection designs. J. Comb. Des. 14, 251269 (2006).

[21] Lee J., Stinson D.R.: On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs. ACM Trans. Inf. Syst. Secur. 11(2), article No. 1 (2008).

[22] Leung-Yan-Cheong, S.K., Cover, T.M.: Some equivalences between Shannon entropy and Kolmogorov complexity. IEEE Trans. Inf. Theory. 24,331–339 (1978).

[23] Li M., Vitanyi P.M.B.: An Introduction to Kol- ´ mogorov Complexity and Its Applications, third ed., Springer-Verlag, New York, (2008).

[24] Longpre, L., Mocas, S.: Symmetry of informa- ´ tion and one-way functions. Inf. Process. Lett. 46(2), 95–100 (1993).

[25] Longpre, L.,Watanabe, O.: On symmetry of in- ´ formation and polynomial time invertibility. Inf. Comput. 121(1), 14–22 (1995).

[26] Matsumoto, T., Imai, H.: On the Key Predistribution System: A Practical Solution to the Key Distribution Problem, Advances in CryptologyCRYPTO’87, LNCS 239, Springer-Verlag, pp. 185-193, 1987.

[27] Paterson M.B., Stinson D.R.: A unified approach to combinatorial key predistribution schemes for sensor networks. Des. Codes Cryptogr. 71, 433-457.(2014)

[28] Pinto, A.: Comparing notions of computational entropy. Theory Comput Syst. 45,944–962 (2009).

[29] Ruj S., Roy B.: Key predistribution using partially balanced designs in wireless sensor networks. In: Proceedings of ISPA 2007. Lecture Notes in Computer Science, vol. 4742, pp. 431- 445 (2007).

[30] Ruj S., Roy B.: Revisiting key predistribution using transversal designs for a grid-based deployment scheme. Int. J. Distrib. Sens. Netw. 5, 660-674 (2008).

[31] Ruj S., Roy B.: Key predistribution using combinatorial designs for a grid-group deployment scheme in wireless sensor networks. ACM Trans. Sens. Netw. 6(1), article No. 4 (2009).

[32] Ruj S., Seberry J., Roy B.: Key predistribution schemes using block designs in wireless sensor networks. In: 2009 international conference on computational science and engineering, pp. 873- 878 (2009).

[33] Safavi-Naini R., Jiang S.: Unconditionally Secure Conference Key Distribution: Security Notions, Bounds and Constructions. Int. J. Found. Comput. Sci. 22(6), 1369-1393 (2011)

[34] Shannon, C.E.: Communication theory of secrecy systems. Bell Tech. J. 28, 656–715 (1949).

[35] Stinson D.R.: Combinatorial Designs, Constructions and Analysis. Springer, New York (2004).

[36] Tadaki, K., Doi, N.: Cryptography and Algorithmic Randomness. Theory Comput Syst, 56, 544- 580(2015).

[37] Teixeira A., Matos A., Souto A., Antunes L.: Entropy measures vs. kolmogorov complexity. Entropy, 13 (3) 595-611(2011).